using System;

using FineCollection.Intf;


using math = System.Math;
using arrays = System.Array;


namespace FineCollection.Immutable
{
    /// <summary>
    /// Immutable set. 
    /// All items are different, nulls are not allowed.
    /// </summary>
    /// <typeparam name="T">type of an item.</typeparam>
    /// <remarks>
    /// <para>
    /// The default origin index is <b>1</b>, but some constructors
    /// allow to specify the origin index. Possible origin index is
    /// an integer value from <see cref="int.MinValue"/>+1 to <see cref="int.MaxValue"/>.
    /// The <see cref="int.MinValue"/> is a special value and could not be used as an index.
    /// </para>
    /// </remarks>
    public class ImmSortSet<T> : ImmArray<T>, RRandomSet<T>
        where T: System.IComparable<T>
    {
        #region CONSTRUCTORS

        /// <summary>
        /// Makes an immutable set with 2 items.
        /// </summary>
        /// <param name="item1">the first item.</param>
        /// <param name="item2">the second item.</param>
        /// <remarks>
        /// Given items must be different and not null.
        /// </remarks>
        public ImmSortSet(T item1, T item2) 
            : base(1, 2)
        {
            if (item1 == null || item2 == null)
                throw new NullItemsException();

            int z = math.Sign( item1.CompareTo(item2) );
            switch (z)
            {
                case -1:
                    arr[0] = item1;
                    arr[1] = item2;
                    break;
                case +1:
                    arr[0] = item2;
                    arr[1] = item1;
                    break;
                case 0:
                    throw new DuplicatesFoundException();
            }
        }


        /// <summary>
        /// Makes an immutable set with 3 items.
        /// </summary>
        /// <param name="item1">the first item.</param>
        /// <param name="item2">the second item.</param>
        /// <param name="item3">the third item.</param>
        /// <remarks>
        /// Given items must be different and not null.
        /// </remarks>
        public ImmSortSet(T item1, T item2, T item3) 
            : base(1, 3)
        {
            if (item1 == null || item2 == null || item3 == null)
                throw new NullItemsException();

            arr[0] = item1;
            arr[1] = item2;
            arr[2] = item3;

            arrays.Sort(arr);
            CheckForDuplicates();
        }


        /// <summary>
        /// Makes an immutable set with 4 items.
        /// </summary>
        /// <param name="item1">the first item.</param>
        /// <param name="item2">the second item.</param>
        /// <param name="item3">the third item.</param>
        /// <param name="item4">the fourth item.</param>
        /// <remarks>
        /// Given items must be different and not null.
        /// </remarks>
        public ImmSortSet(T item1, T item2, T item3, T item4) 
            : base(1, 4)
        {
            if (item1 == null || item2 == null || item3 == null || item4 == null)
                throw new NullItemsException();

            arr[0] = item1;
            arr[1] = item2;
            arr[2] = item3;
            arr[3] = item4;

            arrays.Sort(arr);
            CheckForDuplicates();
        }


        /// <summary>
        /// Makes an immutable set copying items from the specified array.
        /// </summary>
        /// <param name="items">array with items to make a set.</param>
        /// <remarks>
        /// All items in the given array must be different and not nulls.
        /// </remarks>
        public ImmSortSet(T[] items)
            : base(1, items, items.Length, false)
        {
            CheckForNulls();
            arrays.Sort(arr);
            CheckForDuplicates();
        }


        /// <summary>
        /// Makes an immutable set copying items from the specified array.
        /// Allows to specify the origin index.
        /// </summary>
        /// <param name="firstIndex">the origin index.</param>
        /// <param name="items">array with items to make a set.</param>
        /// <remarks>
        /// All items in the given array must be different and not nulls.
        /// </remarks>
        public ImmSortSet(int firstIndex, T[] items)
            : base(firstIndex, items, items.Length, false)
        {
            CheckForNulls();
            arrays.Sort(arr);
            CheckForDuplicates();
        }


        /// <summary>
        /// Makes a copy of the specified set.
        /// </summary>
        /// <param name="set">an ordered set, not null.</param>
        internal ImmSortSet(ROrderSet<T> set) 
            : base(set is RRandomList<T> ? (set as RRandomList<T>).FirstIndex : 1, set.Count)
        {
            int k = 0;
            foreach (T item in set)
                arr[k++] = item;
        }


        /// <summary>
        /// This constructor is for internal usage only.
        /// </summary>
        /// <param name="array">array with already sorted items.</param>
        /// <param name="count">count of real items in the array.</param>
        /// <param name="takeOwnership">true - use this array as is, 
        ///                             false - copy its content to a new array.</param>
        internal ImmSortSet(T[] array, int count, bool takeOwnership) 
            : base(1, array, count, takeOwnership)
        {}

        #endregion



        #region CHECKERS

        /// <summary>
        /// Check for duplicates the array. Array should be sorted.
        /// </summary>
        private void CheckForNulls()
        {
            for (int i = 0; i < count; i++)
                if (arr[i] == null)
                    throw new NullItemsException();
        }


        /// <summary>
        /// Check for duplicates the array. Array should be sorted.
        /// </summary>
        private void CheckForDuplicates()
        {
            for (int i = 0; i <= count - 2; i++)
                if (arr[i].Equals(arr[i + 1]))
                    throw new DuplicatesFoundException();
        }

        #endregion



        /// <summary>
        /// Checks whether this collection contains the specified item.
        /// </summary>
        /// <para>
        /// Complexity of this function is <b>O(log(n))</b>.
        /// This function uses the binary search 
        /// when the set contains 4 or more items.
        /// </para>
        /// <param name="item">the item to check.</param>
        /// <returns>true - the specified item is in the collection.</returns>
        public bool Contains(T item)
        {
            if (item == null)
                return false;

            switch(count)
            {
                case 0:
                    return false;

                case 1:
                    return arr[0].Equals(item);

                case 2:
                    return arr[0].Equals(item) || arr[1].Equals(item);

                case 3:
                    return arr[0].Equals(item) || arr[1].Equals(item) || arr[2].Equals(item);

                default:
                    int z =
                        arrays.BinarySearch(arr, 0, count, item);
                    return z >= 0;
            }
        }


        /// <summary>
        /// The first item.
        /// Raises an exception when the collection is empty.
        /// </summary>
        /// <exception cref="CollectionIsEmpty">when the collection is empty.</exception>
        public T First
        {
            get
            {
                if (count >= 1)
                    return arr[0];
                else
                    throw new CollectionIsEmpty();
            }
        }

        /// <summary>
        /// The last item.
        /// Raises an exception when the collection is empty.
        /// </summary>
        /// <exception cref="CollectionIsEmpty">when the collection is empty.</exception>
        public T Last
        {
            get
            {
                if (count >= 1)
                    return arr[count-1];
                else
                    throw new CollectionIsEmpty();
            }
        }


        /// <summary>
        /// Origin index (index of the first item).
        /// </summary>
        /// <remarks>
        /// Accessible even if the collection is empty.
        /// </remarks>
        /// <seealso cref="RRandomList{T}.LastIndex"/>
        public int FirstIndex
        {
            get { return firstIndex; }
        }

        /// <summary>
        /// Index of the last item.
        /// </summary>
        /// <remarks>
        /// If the collection is empty, it is a value that less than the <see cref="FirstIndex"/>.
        /// </remarks>
        /// <seealso cref="RRandomList{T}.FirstIndex"/>
        public int LastIndex
        {
            get { return firstIndex + count - 1; }
        }


        /// <summary>
        /// Represents a quick indexed access to the specified item.
        /// </summary>
        /// <remarks>
        /// The given index must be in [ FirstIndex .. LastIndex ] inclusively.
        /// </remarks>
        /// <exception cref="CollectionIsEmpty">when the collection is empty.</exception>
        /// <exception cref="IndexOutOfBoundsException">when index is incorrect.</exception>
        /// <seealso cref="RRandomList{T}.FirstIndex"/>
        /// <seealso cref="RRandomList{T}.LastIndex"/>
        public T this[int index]
        {
            get
            {
                if (count == 0)
                    throw new CollectionIsEmpty();

                int localIndex = index - firstIndex;

                if (0 <= localIndex && localIndex < count)
                    return arr[localIndex];
                else
                    throw new IndexOutOfBoundsException(index, FirstIndex, LastIndex);
            }
        }


        /// <summary>
        /// Looks for the specified item, 
        /// or for the possible position where this item may be placed
        /// if this item is not in the collection.
        /// </summary>
        /// <param name="item">an item to look for, must not be null.</param>
        /// <param name="found">true if found, false otherwise.</param>
        /// <param name="position">
        /// <ul>
        /// <li>if the item is found - the position of this item;</li>
        /// <li>if the item is not found and the set is not empty -
        ///        the position of the nearest item larger than the specified one;</li>
        /// <li>if all items of the set are less than the specified one - 
        ///        the <see cref="RRandomList{T}.LastIndex"/> + 1;</li>
        /// <li>if the set is empty - 
        ///        the <see cref="RRandomList{T}.FirstIndex"/>.</li>
        /// </ul>
        /// </param>
        /// <exception cref="NullItemsException">when the specified item is null.</exception>
        public void Find(T item, out bool found, out int position)
        {
            if (item == null)
                throw new NullItemsException();

            if (IsEmpty)
            {
                found = false;
                position = firstIndex;
                return;
            }

            int index = Array.BinarySearch(arr, 0, count, item);

            found = index >= 0;
            position = firstIndex + (found ? index : ~index);
        }


        /// <summary>
        /// Looks for the specified item.
        /// </summary>
        /// <param name="item">an item to look for, may be null.</param>
        /// <returns>index of the found item, 
        ///          or <see cref="int.MinValue"/> if not found.</returns>
        /// <remarks>
        /// <para>
        /// Uses the binary search algorithm,
        /// so its complexity is <i>o(ln(n))</i>.
        /// </para>
        /// <para>
        /// When the specified item is null or the set is empty - 
        /// does nothing and returns <see cref="int.MinValue"/>.
        /// </para>
        /// </remarks>
        public int IndexOf(T item)
        {
            if (item == null || IsEmpty)
                return int.MinValue;

            int index = Array.BinarySearch(arr, 0, count, item);

            if (index >= 0)
                return firstIndex + index;
            else
                return int.MinValue;
        }


        /// <summary>
        /// Creates a read-only ordered iterator.
        /// </summary>
        /// <returns>ordered iterator.</returns>
        /// <seealso cref="ROrderIterator{T}"/>
        new public ROrderIterator<T> TakeIterator()
        {
            return new OrderIterator<T>(this);
        }



        private class OrderIterator<TT> : ImmArray<T>.ArrIterator<TT>, ROrderIterator<TT>
            where TT: IComparable<TT>
        {
            public OrderIterator(ImmArray<TT> ia, int index) 
                : base(ia, index)
            {}

            public OrderIterator(ImmArray<TT> ia) 
                : base(ia)
            {}


            public JumpResult Jump(TT item)
            {
                if (item == null)
                    throw new NullItemsException();

                if (inBounds)
                {
                    int z = item.CompareTo(Current);
                    if (z < 0) return JumpResult.Before;
                    if (z == 0) return JumpResult.Exactly;
                }

                if (index >= ia.count)
                {
                    return JumpResult.End;
                }

                int jumpIndex = Array.BinarySearch(ia.arr, index+1, ia.count-index-1, item);

                if (jumpIndex >= 0)
                {
                    index = jumpIndex;
                    inBounds = true;
                    return JumpResult.Exactly;
                }
                else
                {
                    index = ~jumpIndex;
                    inBounds = index < ia.count;
                    return inBounds ? JumpResult.Over : JumpResult.End;
                }
            }


            RIterator<TT> RIterator<TT>.Clone()
            {
                return new OrderIterator<TT>(ia, index);
            }
        }

    }
}